import java.util.*;

class Student{
    public String id;
    public Student(String id){
        this.id=id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
public class Test {
    public static void main(String[] args) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int num=1805;
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        System.out.println(roman);
    }



    public static void main12(String[] args) {
        String s="abca";
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        System.out.println(ans);

    }
    public static void main11(String[] args) {
        String s="aab";
        if(s.length()==0){
            return ;
        }
        int[] count=new int[s.length()];
        int[] num=new int[s.length()];
        int k=0;
        int j=0;
        int c=0;
        Set<Character> set=new HashSet<>();
        for(c=0;c<s.length();){
            boolean abb=set.add(s.charAt(c));
            if(abb==false){
                num[k]=(c-j);
                count[k]=j;
                j++;
                c=j;
                k++;
                set.clear();
            }else{
                c++;
            }
        }
        if(c==s.length()){
            num[k]=(c-j);
            count[k]=j;
        }
        if(k==0&&j==0){
            System.out.println(s.length());
            return;
        }
        int max=num[0];
        for (int i = 1; i < num.length; i++) {
            if(max<num[i]){
                max=num[i];
            }
        }
        System.out.println(max);
    }
    public static void main10(String[] args) {
        int[] array=new int[]{3,3,7,8};
        int target=6;
        Map<Integer,Integer>map1=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map1.containsKey(target-array[i])){
                System.out.println(map1.get(target-array[i])+" "+i);
                return;
            }
            map1.put(array[i],i);

        }
    }
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
    public static void main8(String[] args) {
        int[] array=new int[]{3,2,3};
        int target=6;
        Map<Integer,Integer> map1=new HashMap<>();
        for(int i=0;i<array.length;i++){
            map1.put(i,array[i]);
            if(i+1<array.length-1) {
                if (array[i + 1] == target - array[i]) {
                    System.out.println(i + "," + (i + 1));
                    return;
                }
            }
            if(map1.containsValue(target-array[i])){
                for (Map.Entry<Integer,Integer> entry:
                        map1.entrySet()) {
                    if(entry.getValue()==target-array[i]&&entry.getKey()!=i){
                        System.out.println(entry.getKey()+","+i);
                        return;
                    }
                }
            }
        }
    }
    public static void main7(String[] args) {
        int[] array=new int[]{1,1,2,2,3,4,5,5,6};
        Set<Integer> set1=new HashSet<>();
        for (int i = 0; i < array.length; i++) {

        }
    }
    public static void main4(String[] args) {
        int[] array=new int[]{1,1,2,2,3,4,4,5,5,6};

        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.get(array[i])==null){
                map.put(array[i],1);
            }else{
                int val=map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry:
                map.entrySet()) {
            if(entry.getValue()==1){
                System.out.println(entry.getKey());
            }
        }

    }
    public static void main3(String[] args) {
        Set<String> set1=new HashSet<>();
        Set<Integer> set2=new HashSet<>();
        Set<Integer>set3=new HashSet<>();
        int[] array=new int[]{1,2,3,4,4,5,5,6,6};
        for (int i = 0; i < array.length; i++) {
            boolean acc= set3.add(array[i]);
            if(acc==false){
                System.out.println(array[i]);
                return;
            }
        }
        LinkedList<Integer>list2=new LinkedList<>();
        list2.add(1);
        list2.add(2);
        list2.add(2);
        LinkedList<String> list1=new LinkedList<>();
        list1.add("dada");
        list1.add("dada");
        list1.add("dadad");
        set1.addAll(list1);
        set2.addAll(list2);
        System.out.println(set1);
        System.out.println(set2);
    }
    public static void main2(String[] args) {
        Student s1=new Student("1234");
        System.out.println(s1.hashCode());
        Student s2=new Student("1234");
        System.out.println(s2.hashCode());
    }
    public static void main1(String[] args) {
        Map<String,Integer> map=new TreeMap<>();
        map.put("abcd",1);
        map.put("cdff",2);
        map.put("dad",5);
        map.put("da",6);
        Integer a= map.get("abcd");
        Integer b=map.get("dad");
        System.out.println(a);
        System.out.println(b);
        boolean acc= map.containsKey("cdff");
        System.out.println(acc);
        Set<String> keyset=map.keySet();
        System.out.println(keyset);
        Set<Map.Entry<String,Integer>> set=map.entrySet();
        for (Map.Entry<String,Integer> entry:
                set
        ) {
            System.out.println("key:"+entry.getKey()+" "+"value:"+entry.getValue());
        }

        Set<Integer> set1=new HashSet<>();
        set1.add(1);
        set1.add(6);
        set1.add(7);
        set1.add(0);
        int[] array=new int[]{1,2,3,4,6,1,1,2,2};
        Set<int[]> set2=new HashSet<>();

        boolean app=set1.contains(1);
        System.out.println(app);




    }
}